package com.cqs.leetcode;

/**
 * KMP算法
 *
 * JDK API
 * Created by cqs on 2018/4/6.
 */
public class ImplementStr {

    private String pattern;
    private int next[];

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) return -1;
        if ("".equals(needle)) return 0;
        if (haystack.equals("")) return -1;
        this.pattern = needle;
        buildNext(pattern);
        int j = 0;
        int i = 0;
        while (j < haystack.length() && i < needle.length()) {
            if (i == -1 || haystack.charAt(j) == needle.charAt(i)) {
                ++j;
                ++i;
            } else {
                i = next[i];
            }
        }
        System.out.println(i + "\t" + j);
        if (i == needle.length()) {
            return j - i;
        }
        return -1;
    }

    //JDK API
    public int strStr0(String haystack, String needle) {
        if (haystack == null || needle == null) return -1;
        return haystack.indexOf(needle);
    }


    //构建Next数组
    private void buildNext(String pattern) {
        next = new int[pattern.length()];
        int i = 0;
        next[0] = -1;
        int j = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }


    public static void main(String[] args) {
        String patten = "ahhllo";
        String text = "hello";
        ImplementStr implementStr = new ImplementStr();
        int match = implementStr.strStr(text, patten);
        System.out.println("match pos: " + match);

        for (int i = 0; i < implementStr.next.length; i++) {
            System.out.print(implementStr.next[i] + "\t");
        }

    }
}
